package leetcode.dynamic_programming;

import java.util.Arrays;

/**
 * 70. 爬楼梯
 * <p>
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * <p>
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * <p>
 * 注意：给定 n 是一个正整数。
 * <p>
 * 示例 1：
 * <p>
 * 输入： 2
 * 输出： 2
 * 解释： 有两种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶
 * 2.  2 阶
 * <p>
 * 示例 2：
 * <p>
 * 输入： 3
 * 输出： 3
 * 解释： 有三种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶 + 1 阶
 * 2.  1 阶 + 2 阶
 * 3.  2 阶 + 1 阶
 * <p>
 * 类似斐波那锲数列。
 * 数据范围最小化  当我们需要考虑n个台阶的时候，可能走一步 也可能走两步 所以接下来需要考虑 (n-1) +(n-2)的一种出现的可能性  重叠子  很容易就发现了
 * 使用递归  记忆搜索法 ，动态规划。
 */
public class Solution70 {
    //递归实现
    public int climbStairs1(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        return climbStairs1(n - 1) + climbStairs1(n - 2);
    }

    //递归实现 使用记忆搜索法进行记录
    public int climbStairs2(int n) {
        int[] sum = new int[n + 1];
        Arrays.fill(sum, -1);
        return fn2(n, sum);
    }

    private int fn2(int n, int[] sum) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        if (sum[n] == -1) {
            sum[n] = fn2(n - 1, sum) + fn2(n - 2, sum);
        }
        return sum[n];
    }

    /**
     * 动态规划
     *
     * @param n
     * @return
     */
    public int climbStairs3(int n) {
        if (n == 0) {
            return 1;
        }
        int[] sum = new int[n + 1];
        Arrays.fill(sum, -1);
        sum[1] = 1;
        if (n >= 2) {
            sum[2] = 2;
        }

        for (int i = 3; i <= n; i++)
            sum[i] = sum[i - 1] + sum[i - 2];
        return sum[n];
    }
}
